# 规定0和A对应、2和B对应、3和C对应... 那么一个数字字符串比如"000"，就可以转化为"AAA"、"KA"和"AK"。
# 给定一个只有数字字符组成的字符串str，返回有多少种转化结果。


def convert_number(s: str):
    return process(s, 0)


def process(s: str, k: int):
    if k == len(s):
        return 1

    if s[k] > '2' or s[k] == '0':
        return process(s, k+1)
    if s[k] == '1':
        res = process(s, k+1)
        if k + 1 < len(s):
            res += process(s, k+2)
        return res
    if s[k] == '2':
        res = process(s, k + 1)
        if k + 1 < len(s) and s[k] < '6':
            res += process(s, k + 2)
        return res


def convert_number_dp(s: str):
    dp = [1, 2 if s[0] == '1' or s[0] == '2' and s[1] < '6' else 1]
    for i in range(2, len(s)):
        if s[i-1] > '2' or s[i-1] == '0':
            dp.append(dp[i-1])
        if s[i-1] == '1':
            dp.append(dp[i-1] + dp[i-2])
        if s[i-1] == '2':
            dp.append(dp[i-1] if s[i] > '6' else dp[i-1] + dp[i-2])
    return dp[-1]


if __name__ == "__main__":
    print(convert_number_dp("18580"))
